#include <iostream>
#include <cassert>

using namespace std;

double pow(double x, int n);
double pow2(double x, int n);
double sqrt(double x, int n);

int main(){
	double x = 3;
	int n = 2;
	double res = pow(3,5);
	double res2 = pow2(3,5);
	cout << res << "\t" << res2 <<endl;
	return 0;
}

// 求阶乘 先求 pow(n-1)  O(n)
double pow(double x, int n){
	assert(n >= 0);
	if(n == 0)
		return 1;
	return x * pow(x, n - 1);
}

// 求阶乘   先求 x^(n/2)   O(logn)   
// todo 求负数次幂
double pow2(double x, int n){
	assert(n >= 0);
	if(n == 0)
		return 1.0;
	double t = pow2(x, n / 2);
	if(n % 2)					// n 为奇数会舍掉x
		return x * t * t;
	return t * t;
}

// 求根
double sqrt(double x, int n){
	return 1;
}
